#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@Author  :   JingV
@Version :   1.0
@Contact :   None
@License :   None
@Desc    :   None
'''


class Solution:
    def solveNQueens(self, n):
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def backtrack(row):
            if row == n:
                board = generateBoard()
                # 将合法答案插入结果集, 从而生成多个结果
                solutions.append(board)
            else:
                for i in range(n):
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    # 重新赋值操作
                    queens[row] = i
                    # 维护三个数据表
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    backtrack(row + 1)
                    # 1. 当前选择无法生成一个答案, 即如果棋子放在当前位置, 无法生成一个有效答案
                    # 或: 2. 棋子放在当前位置可以生成一个有效答案, 将此位置的棋子移除, 为了生成下一个有效答案
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)
                    
        solutions = list()
        queens = [-1] * n
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        row = ["."] * n
        backtrack(0)
        return solutions


def main():
    solution = Solution()
    tests = [4, 8]
    for n in tests:
        print(solution.solveNQueens(n))


if __name__ == "__main__":
    main()
